1. Field of the Invention
The present invention generally relates to graphical layout. More particularly, the invention relates to systems and methods for improved efficiency of the layout of graphical information.
2. Description of Related Art
As the amount and complexity of data increases, there is a need to better explain the data content and as well as potential relationships suggested by the data. One way in which massive data may be described is through the use of graphs. A graph is any visual representation of information or of relationships between quantities, qualities, or sets of data.
A popular graph used to depict data is the force-directed layout graph. The force-based or force-directed graph utilizes force-directed algorithms for drawing graphs in an aesthetically pleasing way. One of the goals for the force-directed algorithm is to lay out the graph in a manner that is comprehensible to the user so that the user can identify components as well as at least some information regarding relationships in the data. In a force-directed layout, the graph generally positions nodes in two-dimensional or three-dimensional space so that all or most of the edges are of equal length and there are as few crossing edges as possible. Forces may be assigned among the sets of edges and the set of nodes. In one example, the forces assigned to the edges act as springs. In other examples, the nodes may act as electrically charged particles.
Unfortunately, as the amount and the number of dimensions of the data grow, the layout of the graph becomes increasingly complex, slow, and computationally expensive. A bad layout may take a long time to draw and may hide or obscure information or relationships thereby rendering the graph ineffective.
Further, existing systems do not scale. The number of computations in existing systems increases dramatically as the number of nodes increases. For example, the number of computations may be N*N for every N number of nodes. As a result, as the amount of data that must be graphed increases, the graphical layout process may slow to the point that the process is no longer useable. Further, existing systems tend to render obscure, non-optimal layouts as the amount of data and/or dimensions increase.